Modern three-dimensional computer graphics use geometry extensively to describe three-dimensional objects, using a variety of graphical representation techniques. Computer graphics find especially wide use in applications such as computer assisted design ("CAD") programs. Complex smooth surfaces of objects to be displayed may be represented using high level abstractions. Detailed surface geometry may be rendered using texture maps, although providing more realism requires raw geometry, usually in the form of triangle primitives. In modern workstation computer systems, position, color (e.g., red, blue, green and optionally .alpha.), and normal components of these triangles are typically represented as floating point numbers. The treatise Computer Graphics: Principles and Practice (2nd ed.), by Foley, van Dam et al. provides substantial detail as to three-dimensional graphics in general and should be consulted by those wishing further background information.
FIG. 1 depicts a prior art generic video system 10 such as may be used with a computer system to display user-generated images. Using a drawing program, for example, such images may be created with a mouse, trackball or other user input devices 20 for display on a video monitor 30, among other uses. Within the context of the invention to be described, displayed objects 40, 50 typically will have a three-dimensional surface, and commonly a portion of one object may be hidden by a portion of another object. In FIG. 1, for example, a portion of object 40 appears to be in front of a portion of object 50, thus hiding from view the concealed portion of object 50. The portion of object 50 that is hidden from view by another object is termed the hidden surface.
Input data from device 20 typically is coupled to a device bus 60, from where coupling to a video processing system 70 occurs, as well as coupling to as computer system input/output interface unit 80, and a computer system memory controller unit 90. Units 80 and 90 are typically coupled to a system bus 100 that also is coupled to the system central processor unit ("CPU") 110, and to the computer system persistent memory unit 120. Among other tasks, CPU 110 may be involved with processing triangular data representing the three dimensional surface of the object to be displayed on monitor 30.
CPU-processed video information is coupled via system bus 100, memory controller 90, device bus 60 into video system 70. Video system 70 typically includes a graphics accelerator unit 130, a video frame buffer random access memory ("3DRAM") unit 140 (or any other form of RAM video store) and a video control unit 150. Processed video from video system 70 is then coupled to monitor 30, which displays images such as images 40 and 50.
The realism of a computer-displayed image three-dimensional objects depends upon many factors, including rapidly calculating those portions of objects that are visible and those portions that are hidden (e.g., have hidden surfaces). Graphics accelerator unit 130 typically im/plements an algorithm to remove the hidden surface of each object to be displayed.
A so-called Z-buffer unit 160 associated with graphics accelerator unit 130 stores a "Z-value", e.g., a depth-value, for each pixel that is to be rendered and displayed. Pixel values for object 50, for example, should only be overwritten when object 50 is closer to a viewing position than the Z-value that is already stored for that pixel value. There exists an image plane onto which the objects to be viewed are projected, and the Z-buffer must ensure that objects that are far away from the view point are projected behind objects that are closer to the view point. Objects should appear smaller as their distance from the view point increases, and the pixel drawing relationship is represented by a function that is inversely proportional to distance. This concept is commonly what is meant by Z-buffering, and the Z-data may be referred to as Z-buffered primitives.
In practice, the old Z-value for the current pixel being rendered is read from the Z-buffer and is numerically compared with a newly generated Z-buffer value for the current pixel. Depending upon the outcome of the comparison, the old Z-values and color frame buffer pixel values will remain, or will be replaced by the newly calculated values.
After the transformation from model space to view clipping coordinates, the term W refers to a scaled distance along the z-axis from the viewpoint to the transformed point. The value Z refers to a similar scaled distance but one having its origin other than at the viewpoint, typically an origin at the front clipping plane, or a point between the front and back clipping planes. After the transformation from view clipping coordinates to screen coordinates, the value of Z is derived from the quantity Z/W. For orthographic projection, the value Z/W is linear in the distance to the point in world coordinates. For perspective projection, this Z/W value is linear in the reciprocal of the distance to the point.
Early three-dimensional computer graphics was most concerned with so-called "orthographic projections", in which objects would not diminish in size with increasing distance from the viewpoint (so-call ed "infinite parallel projection"). In orthographic projections, the value of Z used for eliminating hidden surfaces was linear in the distance to the point in world coordinates. In such application, numeric representation using either fixed point or floating point well matched the numeric values produced by the math.
But as three-dimensional computer graphics adopted "perspective projection", the underlying historically developed equations and numeric representations were not changed, even though such numerical representations were no longer well matched to the mathematics involved. To understand why, it is necessary to recall that in the perspective case, the calculated screen space Z value is linear in the reciprocal of world coordinate distance. The equations used in the prior art produced a screen space Z value related to the world space distance as follows: EQU Z=(1/(1-F/B))*(1-F/Z) (1)
For large B/F ratios: EQU Z.apprxeq.1-F/Z (1')
B/F represents the ratio of distance in world coordinates from the viewpoint to the back clipping plane, to the distance from the viewpoint to the front clipping plane. FIG. 2A depicts the front and back clipping planes denoted as F and B respectively. At the left of FIG. 2A, the "0" represents the eye of the viewer observing the representations of the displayed objects, e.g., refers to the viewpoint. In FIG. 2A, 40 and 50 represent the relative position of two objects, perhaps objects similar to what was displayed on monitor 30 in FIG. 1.
The B/F ratio plays an important role in the relevant mathematical relationships. In the early days of perspective projection three-dimensional computer graphics, the B/F ratio was typically a small integer. Commonly, the front clipping plane would be two feet from the viewpoint, and the back clipping plane would be four to ten feet away. This configuration was sufficient to view three-dimensional objects having an apparent size of a few feet, suspended in a black background.
However, more modern and realistic large scale virtual environments may dictate that the front clipping plane is but a few inches from the viewer's nose, while the back clipping plane may be miles away. For this configuration, very large B/F ratios result. For example, a front clipping plane at six inches and a rear clipping plane at ten miles produces a B/F ratio exceeding 100,000. Even smaller ranges of six inches and six hundred feet can still produce ratios exceeding 1,000.
The standard screen space Z equation (1) is defined such that points near the front clipping plane F produce a Z value near zero, and points near the back clipping plane B produce a Z value near one (or, using a slightly different equation, -1 and 1, or 1 and -1).
In considering the numerical suitability of a particular equation, it is important to examine how values represented in the input are represented at the output. Consider the particular case of B/F=1,024. In screen space, using equation (1), any points located in the back half of this range (more than halfway toward the back clipping plane) will have ten leading one digits before any other distance-representing bits begin, e.g., a form .1111111111xxx . . . xxx. Thus in world coordinates, any points requiring n bits of accuracy to represent a value between B/2 and B, will require 10+n bits of accuracy for screen space representation, if equation (1) is used. In general, equation (1) requires approximately the ceiling(log.sub.2 (B/F)) additional bits for screen space representation. For example, a B/F ratio of 100,000 will require an additional 17 bits.
Note that the above representation loss affects both fixed point and floating point representations. While floating point representations are efficient at encoding values having leading zero bits, because the screen space Z value of points near the back clipping plane is mapped to one, the extra bits generated are leading one bits.
Although many three-dimensional graphics processors compute equation (1) using floating point representation, for reasons of cost, subsequent setup and scan conversion steps are almost always computed using fixed point representations.
Delay and inaccuracy in calculating proper Z-buffered primitives can result in an erroneous display of the relevant objects. For example, in FIG. 1, displayed objects 40 and/or 50 (among other objects now depicted for ease of illustration) may be moved about, perhaps rotated, changed in size, etc. Thus, realism dictates the necessity to rapidly provide Z-buffer data. Z-buffer data that is too inaccurately calculated can degrade the realism of the displayed image.
In FIG. 1, for example, the apple object 40 appears to be in front of, e.g., closer to the viewing position (and thus having smaller Z-buffer values) the box 50. However, the realism of the display would be destroyed if Z-buffer data for the hidden surface of the box were erroneously calculated say for only the bottom front edge of the box. The resultant display should show the apple in front of the box, except that the bottom front edge of the box would incongruously be in front of the apple.
When Z-buffered data is properly calculated, images 40 and 50 will be displayed as shown in FIG. 1, wherein the apple 40 is in front of the box 50. FIG. 2B depicts the proper projected image representation for these two images. However, in a Z/F distance regime in which Z-buffered data becomes too inaccurate, errors can occur. Thus, in FIG. 2C, rather than over-write underlying pixel data for the concealed surface of box 50, prior art Z-buffer unit 160 has erroneously decided to simultaneously paint pixels for object 40 and for object 50. The result is an overlay region in which one or both of the objects may appear to be ragged overlaid, known as "Z-buffer fighting". FIG. 2D shows yet another type of display error resulting from incorrect Z-buffering, according to the prior art. In FIG. 2D a portion of box 50 erroneously appears solidly in front of a portion of apple 40, yet a portion of box 50 appears raggedly overlaid relative to apple 40, as well.
It is apparent that resolution loss problems when using fixed-point integer calculations of the type defined by the above equations are very dependent upon the B/F ratio. Assume that the ratio of B/F is M, that is the front plane is at distance F and the backplane is at distance MF. Consider now when the distance to the backplane is doubled, e.g., the backplane is now at distance 2MF. For each such distance doubling, another bit of resolution is lost, leaving potentially too few bits to resolve the remaining distances in the far half of the Z-buffer, e.g., between MF and 2MF. Assuming a Z-representation of n bits maximum, points at distance between 1F and 2F will be represented with n-1 bits of accuracy. Points between 2F and 4F will be represented with at most n-2 bits of accuracy, and so on. Thus the bits remaining may be insufficient to adequately resolve distances between obscuring objects, giving rise to incorrect calculation and display of hidden surfaces. It is now seen that for large B/F ratios, large numbers of bits of accuracy can be lost.
In summation, there is a need for a mechanism to accurately calculate Z-buffered values for displayed graphic objects, without imposing a non-linear loss of bits over different distant ranges. To better accommodate modern workstation computer systems, such Z-buffering preferably should implement an equation different than equation (1), and should use a floating point format. Preferably such Z-buffering should be capable of implementation using off-the-shelf generic components.
The present invention discloses such Z-buffering.